#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// 快速幂，计算 x^e mod m
ll mod_pow(ll x, ll e, ll m) {
    __int128 base = x % m, res = 1;
    while (e) {
        if (e & 1) res = (res * base) % m;
        base = (base * base) % m;
        e >>= 1;
    }
    return (ll)res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        ll m;
        cin >> n >> m;
        // M1 = m * MOD，用于双重模
        ll M1 = m * (__int128)MOD;

        ll sum_mod = 0;  // W mod M1
        for (int i = 0; i < n; i++) {
            ll a, b;
            cin >> a >> b;
            // term = a * 2^b mod M1
            ll t1 = a % M1;
            ll t2 = mod_pow(2, b, M1);
            sum_mod = (sum_mod + (__int128)t1 * t2 % M1) % M1;
        }

        // 余数 r = W mod m
        ll r = sum_mod % m;
        // 商 q = (W - r) / m, 在 M1 范围内整除安全
        ll q_mod = ((sum_mod - r) / m) % MOD;

        // 答案 k = q + (r>0?1:0)
        ll ans = q_mod + (r > 0 ? 1 : 0);
        if (ans >= MOD) ans -= MOD;
        cout << ans << "\n";
    }
    return 0;
}
